import java.util.Scanner;
import java.util.Arrays;

// Name: Sudoku | 2018 - 2022
// Version: 1.0
// Last update: 2022.3.16
// ----------------------------------------
// Developer: Monkeyhbd | 2017 - 2022
// Email: monkeyhbd@163.com
// ----------------------------------------
//
//                         ##
//                         ##    ##    ####    ##    ##    ##      ##          ##
//     ##  ##      ####    ##  ##    ##    ##    ##  ##    ##      ##          ##
//   ##  ##  ##  ##    ##  ####      ########      ##      ####    ####      ####
//   ##  ##  ##  ##    ##  ##  ##    ##            ##      ##  ##  ##  ##  ##  ##
//   ##  ##  ##    ####    ##    ##    ####      ##        ##  ##  ####      ####
//
// ----------------------------------------
// License: GNU GPLv2

public class Main
{
	static boolean[][][] sudoku = new boolean[9][9][9];

	static int array_read(boolean[] arr)
	{
		int num = 0, c = 0;
		for (int idx = 0; idx < 9; idx += 1)
		{
			if (arr[idx])
			{
				num = idx + 1;
				c += 1;
			}
		}
		if (c == 0)
		{
			return -1;  // Error.
		}
		else if (c == 1)
		{
			return num;
		}
		else
		{
			return 0;  // Not resolved.
		}
	}

	static int array_count(boolean[] arr)
	{
		int c = 0;
		for (int idx = 0; idx < 9; idx += 1)
		{
			if (arr[idx])
			{
				c += 1;
			}
		}
		return c;
	}

	static int sudoku_unit_count(boolean[][] sudoku_unit)
	{
		int c = 0;
		for (int idx = 0; idx < 9; idx += 1)
		{
			c += array_count(sudoku_unit[idx]);
		};
		return c;
	}

	static int sudoku_count(boolean[][][] sudoku)
	{
		int c = 0;
		for (int idx = 0; idx < 9; idx += 1)
		{
			c += sudoku_unit_count(sudoku[idx]);
		}
		return c;
	}

	static void array_write(boolean[] arr, int num)
	{
		if (0 < num && num < 10)
		{
			for (int idx = 0; idx < 9; idx += 1)
			{
				arr[idx] = false;
			}
			arr[num-1] = true;
		}
		else
		{
			for (int idx = 0; idx < 9; idx += 1)
			{
				arr[idx] = true;
			}
		}
	}

	static void print_sudoku_unit(boolean[][] sudoku_unit)
	{
		for (int idx = 0; idx < 9; idx += 1)
		{
			System.out.print("[" + array_read(sudoku_unit[idx]) + "] ");
		}
		System.out.println();
	}

	static void print_sudoku(boolean[][][] sudoku)
	{
		for (int idx = 0; idx < 9; idx += 1)
		{
			print_sudoku_unit(sudoku[idx]);
		}
	}

	static void str2sudoku_unit(String str, boolean[][] sudoku_unit)
	{
		for (int idx = 0; idx < 9; idx += 1)
		{
			int num = str.charAt(idx) - '0';
			array_write(sudoku_unit[idx], num);
		}
	}

	static void user_input()
	{
		Scanner input = new Scanner(System.in);
		for (int idx = 0; idx < 9; idx += 1)
		{
			System.out.print("Line" + (idx + 1) + ": ");
			String str = input.next();
			str2sudoku_unit(str, sudoku[idx]);
		}
		input.close();
	}

	static void test_input(String[] ipts)
	{
		for (int idx = 0; idx < 9; idx += 1)
		{
			str2sudoku_unit(ipts[idx], sudoku[idx]);
		}
	}

	static boolean check_unit(boolean[][] sudoku_unit)
	{
		boolean[] board = new boolean[9];
		for (int idx = 0; idx < 9; idx += 1)
		{
			int num = array_read(sudoku_unit[idx]);
			if (num < 1)
			{
				continue;
			}
			if (board[num-1])
			{
				return false;
			}
			else
			{
				board[num-1] = true;
			}
		}
		return true;
	}

	static boolean check(boolean[][][] sudoku)
	{
		// Line
		for (int idx = 0; idx < 9; idx += 1)
		{
			if (!check_unit(sudoku[idx]))
			{
				return false;
			}
		}

		// Column
		for (int idx = 0; idx < 9; idx += 1)
		{
			boolean[][] tmp_unit = new boolean[9][9];
			for (int x = 0; x < 9; x += 1)
			{
				tmp_unit[x] = sudoku[x][idx];
			}
			if (!check_unit(tmp_unit))
			{
				return false;
			}
		}

		// Box
		for (int idx = 0; idx < 9; idx += 1)
		{
			boolean[][] tmp_unit = new boolean[9][9];
			int x = idx % 3 * 3, y = idx / 3 * 3;
			for (int j = 0; j < 3; j += 1)
			{
				for (int i = 0; i < 3; i += 1)
				{
					tmp_unit[j*3+i] = sudoku[y+j][x+i];
				}
			}
			if (!check_unit(tmp_unit))
			{
				return false;
			}
		}

		return true;
	}

	static void exclusion_unit(boolean[][] sudoku_unit)
	{
		int last_sum = -1, this_sum = sudoku_unit_count(sudoku_unit);
		while (last_sum != this_sum)
		{
			last_sum = this_sum;
			for (int idx = 0; idx < 9; idx += 1)
			{
				int num = array_read(sudoku_unit[idx]);
				if (num > 0)
				{
					for (int x = 0; x < 9; x += 1)
					{
						sudoku_unit[x][num-1] = false;
					}
					sudoku_unit[idx][num-1] = true;
					this_sum += 1;
				}
			}
			this_sum = sudoku_unit_count(sudoku_unit);
		}
	}

	static void look_unit(boolean[][] sudoku_unit)
	{
		int[] counter = {0, 0, 0, 0, 0, 0, 0, 0, 0};

		for (int idx = 0; idx < 9; idx += 1)
		{
			if (array_read(sudoku_unit[idx]) == 0)
			{
				for (int x = 0; x < 9; x += 1)
				{
					if (sudoku_unit[idx][x])
					{
						counter[x] += 1;
					}
				}
			}
		}

		for (int x = 0; x < 9; x += 1)
		{
			if (counter[x] == 1)
			{
				for (int idx = 0; idx < 9; idx += 1)
				{
					if (sudoku_unit[idx][x])
					{
						array_write(sudoku_unit[idx], x + 1);
					}
				}
			}
		}
	}

	static void exclusion(boolean[][][] sudoku)
	{
		int last_sum = -1, this_sum = sudoku_count(sudoku);
		while (last_sum != this_sum)
		{
			last_sum = this_sum;
			// Line
			for (int idx = 0; idx < 9; idx += 1)
			{
				exclusion_unit(sudoku[idx]);
				look_unit(sudoku[idx]);
			}

			// Column
			for (int idx = 0; idx < 9; idx += 1)
			{
				boolean[][] tmp_unit = new boolean[9][9];
				for (int x = 0; x < 9; x += 1)
				{
					tmp_unit[x] = sudoku[x][idx];
				}
				exclusion_unit(tmp_unit);
				look_unit(tmp_unit);
			}

			// Box
			for (int idx = 0; idx < 9; idx += 1)
			{
				boolean[][] tmp_unit = new boolean[9][9];
				int x = idx % 3 * 3, y = idx / 3 * 3;
				for (int j = 0; j < 3; j += 1)
				{
					for (int i = 0; i < 3; i += 1)
					{
						tmp_unit[j*3+i] = sudoku[y+j][x+i];
					}
				}
				exclusion_unit(tmp_unit);
				look_unit(tmp_unit);
			}
			this_sum = sudoku_count(sudoku);
		}
	}

	static boolean enumeration_core(boolean[][][] sudoku, boolean[][][] sudoku_backup, int[][] position, int idx, int idx_max)
	{
		if (idx < idx_max)
		{
			for (int x = 0; x < 9; x += 1)
			{
				if (sudoku_backup[position[idx][1]][position[idx][0]][x])
				{
					array_write(sudoku[position[idx][1]][position[idx][0]], x + 1);
					if (check(sudoku))
					{
						boolean rtn = enumeration_core(sudoku, sudoku_backup, position, idx + 1, idx_max);
						if (rtn)
						{
							return true;
						}
					}
				}
			}
			for (int i = 0; i < 9; i += 1)
			{
				sudoku[position[idx][1]][position[idx][0]][i] = true;
			}
			return false;
		}
		else
		{
			for (int x = 0; x < 9; x += 1)
			{
				if (sudoku_backup[position[idx][1]][position[idx][0]][x])
				{
					array_write(sudoku[position[idx][1]][position[idx][0]], x + 1);
					if (check(sudoku))
					{
						return true;
					}
				}
			}
			for (int i = 0; i < 9; i += 1)
			{
				sudoku[position[idx][1]][position[idx][0]][i] = true;
			}
			return false;
		}
	}

	static void enumeration(boolean[][][] sudoku)
	{
		boolean[][][] sudoku_backup = new boolean[9][9][9];
		for (int y = 0; y < 9; y += 1)
		{
			for (int x = 0; x < 9; x += 1)
			{
				for (int idx = 0; idx < 9; idx += 1)
				{
					sudoku_backup[y][x][idx] = sudoku[y][x][idx];
				}
			}
		}

		int[][] position = new int[81][2];
		int idx = 0;
		for (int y = 0; y < 9; y += 1)
		{
			for (int x = 0; x < 9; x += 1)
			{
				if (array_read(sudoku_backup[y][x]) == 0)
				{
					position[idx][0] = x;
					position[idx][1] = y;
					idx += 1;
				}
			}
		}

		enumeration_core(sudoku, sudoku_backup, position, 0, idx - 1);
	}

	static void solution(boolean[][][] sudoku)
	{
		exclusion(sudoku);
		enumeration(sudoku);
	}

	public static void main(String[] args)
	{
		user_input();

		long t0 = System.currentTimeMillis();

		solution(sudoku);

		long te = System.currentTimeMillis();

		System.out.println();
		print_sudoku(sudoku);

		System.out.println();
		double millis = te - t0;
		System.out.printf("The Java program use %.6f s.\n", millis / 1000);
	}
}

